\section{Appendix~\ref{app:s:3agents}: Proofs Missing from Section~\ref{s:3agents}}
\label{app:s:3agents}

\subsection{The Proof of Lemma~\ref{l:single-p}}
\label{app:s:single-p}

Let $i \in \{ 1, 2, 3\}$ be any agent and $a \in \reals$ be any location. By Proposition~\ref{prop:interval}, for every $(i|j,k)$-well-separated instance $\vec{z}$ with $z_i = a$, $F_2(\vec{z}) \in [z_j, z_k]$. We distinguish between the case where there is an $(i|j,k)$-well-separated instance $\vec{z}$ with $z_i = a$ and $F_2(\vec{z}) \in (z_j, z_k)$, and the case where for all $(i|j,k)$-well-separated instances $\vec{z}$ with $z_i = a$, $F_2(\vec{z}) \in \{ z_j, z_k \}$.

\smallskip\noindent {\bf Case I: $\exists \vec{z}\,F_2(\vec{z}) \in (z_j, z_k)$.}
%
Let $\vec{z}$ be any $(i|j,k)$-well-separated instance with $z_i = a$ and $F_2(\vec{z}) \in (z_j, z_k)$. In this case, we let $p = F_2(\vec{z})$. Next, we show that for any $(i | j, k)$-well-separated instance $\vec{x}$ with $x_i = a$\,:
%
\begin{equation}\label{eq:p-median}
 F_2(\vec{x}) = \left\{\begin{array}{ll}
 x_k\ \ \ & \mbox{if $x_k \leq p$}\\
%
 x_j & \mbox{if $p \leq x_j$}\\
%
 p & \mbox{if $x_j < p < x_k$}
\end{array}\right.
\end{equation}
%
This implies the existence of a unique point $p \in (a, +\infty)$, such that
for all $(i | j, k)$-well-separated instances $\vec{x}$ with $x_i = a$, $F_2(\vec{x}) = \med(p, x_j, x_k)$.

For the first two cases of (\ref{eq:p-median}), we consider the instances $\vec{z}' = (\vec{z}_{-k}, p)$ and $\vec{z}'' = (\vec{z}_{-j}, p)$, which are both $(i | j, k)$-well-separated.
%
Since $F$ is strategyproof, $F_2(\vec{z}') = p = z'_k$. Then, by Proposition~\ref{prop:left_cover}, for every $(i | j, k)$-well-separated instance $\vec{x} = (\vec{z}_{-\{j,k\}}, x_j, x_k)$ with $x_k \leq p$, $F_2(\vec{x}) = x_k$.
%
Similarly, $F_2(\vec{z}'') = p = z''_j$, and by Proposition~\ref{prop:right_cover}, for every $(i | j, k)$-well-separated instance $\vec{x} = (\vec{z}_{-\{j,k\}}, x_j, x_k)$ with $x_j \geq p$, $F_2(\vec{x}) = x_j$.

For the third case of (\ref{eq:p-median}), we assume that there is an $(i | j, k)$-well-separated instance $\vec{x}$ with $x_i = a$, $x_j < p < x_k$, and $F_2(\vec{x}) = q \neq p$, and reach a contradiction (i.e., this case essentially establishes the uniqueness of $p$). Without loss of generality, we assume that $q > p$ (the case where $q < p$ is symmetric), and let $\eps \in (0, (q-p)/2)$ be appropriately small. To reach a contradiction, we exploit two $(i | j, k)$-well-separated instances, $\vec{y}$ and $\vec{y}'$, with $y_i = y'_i = a$, $y_j = x_j$, $y_k = q$, $y'_j = p$, and $y'_k = p+\eps$, such that $F_2(\vec{y}) = q = y_k$ and $F_2(\vec{y}') = p = y'_j$. Since $\vec{y}$ is an $(i | j, k)$-well-separated instance with $F_2(\vec{y}) = y_k$, Proposition~\ref{prop:left_cover} implies that for the $(i|j,k)$-well-separated instance $\vec{y}' = (\vec{y}_{-\{j,k\}}, p, p+\eps)$, with $y'_k < y_k$, $F_2(\vec{y}') = y'_k \neq p$, a contradiction.

To conclude the proof, it remains to show that indeed $F_2(\vec{y}) = q$ and $F_2(\vec{y}') = p$. To this end, we recall that $q \in [x_j, x_k]$, by Proposition~\ref{prop:interval}. For the former instance $\vec{y} = (\vec{x}_{-k}, q)$, we observe that it is $(i | j, k)$-well-separated because the distance of $x_j$ to $q$ is no greater than the distance of $x_j$ to $x_k$, and that $F_2(\vec{y}) = q$, because $F_2(\vec{x}) = q$ and $F$ is strategyproof. The latter instance $\vec{y}' = (\vec{z}_{-\{j, k\}}, p, p+\eps)$ is also $(i | j, k)$-well-separated, because $p > z_j$ and $\eps$ is chosen sufficiently small. Furthermore, $F_2(\vec{y}') = p$, because $F_2(\vec{z}) = p$, by hypothesis, $F_2(\vec{z}_{-j}, p) = p$, by $F$'s strategyproofness, and $F_2(\vec{z}_{-\{j,k\}}, p, p+\eps) = p$, by Proposition~\ref{prop:c_pulls_b}, because the instance $(\vec{z}_{-j}, p)$ is $(i|j,k)$-well-separated.


\smallskip\noindent {\bf Case II: $\forall \vec{z}\,F_2(\vec{z}) \in \{z_j, z_k\}$.}
%
Let $\vec{z}$ be any $(i|j,k)$-well-separated instance with $z_i = a$. We let $p = a$, if $F_2(\vec{z}) = z_j$\,%
%
\footnote{The uniqueness of $p$ for the case where $p = a$ follows from the fact that there are $(i|j,k)$-well-separated instances $\vec{z}$ with $z_i = a$ and $z_j$ arbitrarily close to $a$.},
%
and $p = \uparrow$, if $F_2(\vec{z}) = z_k$.
%
To conclude the proof, we show that if ($F_2(\vec{z}) = z_j$ and thus) $p = a$, for all $(i | j, k)$-well-separated instances $\vec{x}$ with $x_i = a$, $F_2(\vec{x}) = x_j$ (the case where $p = \uparrow$ and $F_2(\vec{x}) = x_k$ is symmetric).

To reach a contradiction, let us assume that there is a $(i|j,k)$-well-separated instance $\vec{x}$ with $x_i = a$ and $F_2(\vec{x}) \neq x_j$. Therefore, since we have assumed that $F_2(\vec{x}) \in \{x_j, x_k\}$, $F_2(\vec{x}) = x_k$. By Proposition~\ref{prop:b_pulls_c}, we can assume without loss of generality that $x_j$ can be arbitrarily close to $x_k$ (as long as $x_j$ stays on the left of $x_k$, so that $\vec{x}$ is $(i|j,k)$-well-separated). By Proposition~\ref{prop:right_cover}, for all $(i|j,k)$-well-separated instances $\vec{x}'$ with $x'_i = z_i = a$ and $z_j \leq x'_j$, $F_2(\vec{x}') = x'_j$. Therefore, we can assume that $x_j < z_j$, and since $x_j$ can be arbitrarily close to $x_k$, $x_j < x_k < z_j$. To conclude the proof, we show the following technical claim, which states that the existence of such an instance $\vec{x}$ implies that for all $(i|j,k)$-well-separated instances $\vec{y}$ with $y_i = a$ and $y_k > x_k$, $F_2(\vec{y}) = y_k$, a contradiction to the existence of $\vec{z}$.

\begin{claim}\label{cl:moving-backwards}
Let $F$ be any nice mechanism, let $i$ be any agent, and let $a$ be any location of $i$ such that for all $(i|j,k)$-well-separated instances $\vec{z}$ with $z_i = a$, $F_2(\vec{z}) \in \{z_j, z_k\}$. Then, if there exists an $(i|j,k)$-well-separated instance $\vec{x}$ with $x_i = a$ and $F_2(\vec{x}) = x_k$, for all $(i|j,k)$-well-separated instances $\vec{x}' = (\vec{x}_{-\{j,k\}}, x'_j, x'_k)$ with $x_k < x'_k$, $F_2(\vec{x}') = x'_k$.
\end{claim}

\begin{proof}[of Claim~\ref{cl:moving-backwards}]
We first show that for all $(i|j,k)$-well-separated instances $\vec{y} = (\vec{x}_{-\{j, k\}}, y_j, y_k)$ with $x_j \leq y_j < x_k < y_k$, $F_2(\vec{y}) = y_k$. For sake of contradiction, let us assume that there exists such an instance $\vec{y}$ for which $F_2(\vec{y}) \neq y_k$.
%
To establish a contradiction, we first observe that for the instance $\vec{x}' = (\vec{x}_{-j}, y_j)$, $F_2(\vec{x}') = x_k$, by Proposition~\ref{prop:b_pulls_c}, since $\vec{x}'$ is an $(i|j,k)$-well-separated instance.
%
Since $\vec{y} = (\vec{x}'_{-k}, y_k)$ and $F_2(\vec{y}) \neq y_k$, there exists a $y_k$-hole $(l, r)$ in the imageset $I_k(y_i, y_j)$ with $x_k \leq l < y_k$. Let $y'_k \in (l, y_k)$ be any point in the left half of the hole $(l, r)$, i.e. let $y'_k = \min\{ (y_k + 2l) / 3, (r+2l)/ 3 \}$. Due to $F$'s strategyproofness, $F_2(\vec{y}_{-k}, y'_k) = l$, because $l$ is the closest point to $y'_k$ in $I_k(y_i, y_j)$. This contradicts the hypothesis, since we have found an $(i|j,k)$-well-separated instance $\vec{y}' = (\vec{y}_{-k}, y'_k)$ with $F_2(\vec{y}') \not\in \{y'_j, y'_k\}$.

To conclude the proof, we inductively apply what we have shown above: namely that if for some $(i|j,k)$-well-separated instance $\vec{x}$, $F_2(\vec{x}) = x_k$, then for all $(i|j,k)$-well-separated instances $\vec{y} = (\vec{x}_{-\{j, k\}}, y_j, y_k)$ with $x_j \leq y_j < x_k < y_k$, $F_2(\vec{y}) = y_k$. The proof is similar to the proofs of Proposition~\ref{prop:right_cover} and Proposition~\ref{prop:left_cover}.

Let $x'_k > x_k$ be any point, let $d = x'_k - x_k$, let $\delta = (x_k - x_j)/2$, and let $\kappa = \ceil{d/\delta}$. For every $\l = 1, \ldots, \kappa, \kappa+1$, we inductively consider the instance $\vec{x}_\lambda = (\vec{x}_{-\{j, k\}}, x_j + (\lambda-1) \delta, x_k + (\lambda-1)\delta)$.
%
We observe that the instance $\vec{x}_\lambda$ is $(i | j, k)$-well-separated, because the distance of the locations of agents $j$ and $k$ is $2\delta$, while the distance of the locations of agents $i$ and $j$ is at least their distance in $\vec{x}$.
%
Therefore, for every $\l = 1, \ldots, \kappa, \kappa+1$, $F_2(\vec{x}_\lambda) = x_k + (\lambda-1)\delta$. Moreover, by Proposition~\ref{prop:left_cover}, for any $(i|j,k)$-well-separated instance $\vec{y} = (x_i, y_j, y_k)$ with $y_k \leq
x_k + \kappa\delta$, $F_2(\vec{y}) = y_k$. Therefore, since $x'_k \leq x_k + \kappa\delta$, for all $(i|j,k)$-well-separated instances $\vec{x}' = (\vec{x}_{-\{j,k\}}, x'_j, x'_k)$ with $x_k < x'_k$, $F_2(\vec{x}') = x'_k$.
\qed\end{proof}


\subsection{The Proof of Lemma~\ref{l:i-separated}}
\label{app:s:i-separated}

By Lemma~\ref{l:single-p}, for any agent $i \in \{1, 2, 3\}$ and any location $a \in \reals$\,:
%
\begin{itemize}
\item there is a unique $p_1 \in [a, +\infty) \union \{ \uparrow \}$ such that for any $(i | j, k)$-well-separated instance $\vec{x}$ with $x_i = a$, $F_2(\vec{x}) = \med(p_1, x_j, x_k)$, and

\item there is a unique $p_2 \in [a, +\infty) \union \{ \uparrow \}$ such that for any $(i | k, j)$-well-separated instance$\vec{x}$ with $x_i = a$, $F_2(\vec{x}) = \med(p_2, x_j, x_k)$.
\end{itemize}

We observe that it suffices to show that either $p_1 =\,\uparrow$ or $p_2 =\,\uparrow$. More specifically, if $p_1 =\,\uparrow$, then the preferred agent is $k$ and $p = p_2$. Then, if $x_k \geq p_2$, we distinguish between two cases depending on the order of $x_j$ and $x_k$. If $x_k \leq x_j$, then $\vec{x}$ is an $(i | k, j)$-well-separated instance, and $F_2(\vec{x})$ is located at the median of $p_2, x_k, x_j$, that is $x_k$. If $x_k > x_j$, $\vec{x}$ is an $(i | j, k)$-well-separated instance, and $F_2(\vec{x})$ is located at the median of $x_j, x_k, p_1$, that is $x_k$, because $p_1 =\,\uparrow$.
%
If $x_k < p_2$, we again distinguish between two cases. If $x_k \leq x_j$, then $\vec{x}$ is an $(i | k, j)$-well-separated instance, and $F_2(\vec{x}) = \med(p_2, x_k, x_j)$. If $x_k > x_j$, $\vec{x}$ is an $(i | j, k)$-well-separated instance, and $F_2(\vec{x})$ is located at the median of $x_j, x_k, p_1$, which coincides with $\med(x_j, x_k, p_2)$, because $p_1 =\,\uparrow$ and $p_2 > x_k > x_j$. If $p_2 =\,\uparrow$, then the preferred agent is $j$ and $p = p_1$, and the lemma follows from a similar analysis.

We proceed to establish that either $p_1 =\,\uparrow$ or $p_2 =\,\uparrow$. To reach a contradiction, we assume that both $p_1, p_2 \in [a, +\infty)$. Let $\vec{x}$ be an $(i| j, k)$-well-separated instance where both $x_j$ and $x_k$ exceed $\max\{ p_1, p_2\}$. Then, by Lemma~\ref{l:single-p}, $F_2(\vec{x}) = \med(p_1, x_j, x_k) = x_j$. Since $F_2(\vec{x}) \neq x_k$, there is a $x_k$-hole $(l, r)$ in the image set $I_k(x_i, x_j)$. For some appropriately small $\eps > 0$, we consider the instances $\vec{x}' = (\vec{x}_{-k}, r-\eps)$ and $\vec{x}'' = ({\vec{x}'}_{-j}, r)$. Since $r \in I_k(x_i, x_j)$, $F_2(\vec{x}') = r$. Since $r \in I_j(x_i, r-\eps)$, $F_2(\vec{x}'') = r$. On the other hand, since $\eps$ is chosen appropriately small, the instance $\vec{x}''$ is $(i|k, j)$-well-separated. Therefore, by Lemma~\ref{l:single-p}, $F_2(\vec{x}'') = \med(p_2, r-\eps, r) \neq r$, a contradiction. \qed



\subsection{The Proof of Corollary~\ref{cor:dict-location}}
\label{app:s:dict-location}

The corollary states that for any $(i|j,k)$-well-separated instance $\vec{x}$, the rightmost facility is allocated to the middle agent $j$ only if $j$ is the preferred agent of $(i, x_i)$ and is located on the left of $(i, x_i)$'s threshold. This can be easily verified by Fig.~\ref{fig:allocation}.a, where the rightmost facility is never allocated to $k$ below the $x_j = x_k$ line, where $k$ is the middle agent, and is allocated to the preferred agent $j$ above the $x_j = x_k$ line, where $j$ is the middle agent, only on the right of $p$.

We also give a more formal argument. For convenience, we let $p_i \equiv \l_p(i, x_i)$. We first observe that if $\l_\ell(i, x_i) = k$, $F_2(\vec{x}) = x_k$. This follows from Lemma~\ref{l:i-separated}, because $x_j < x_k$. More specifically, either $x_k \geq p_i$, and the rightmost facility is allocated to $k$, as the preferred agent, or $x_k < p_i$, and the rightmost facility is allocated to $x_k$, as the median of $p_i$, $x_j$, and $x_k$. Hence, $\l_\ell(i, x_i) = j$.
%
Moreover, if $p_i > x_j$, $F_2(\vec{x}) = \med(p_i, x_j, x_k) > x_j$, by the second case of Lemma~\ref{l:i-separated}. Therefore, $p_i \leq x_j$.
\qed



\subsection{The Proof of Lemma~\ref{l:non-separated-inside}}
\label{app:s:non-separated-inside}

%Let us fix an agent $i$ and a location $a \in \reals$. By Lemma~\ref{l:i-separated}, there are a threshold $p \in [a, +\infty) \union \{ \uparrow \}$ such that for any $i$-left-well-separated instance $\vec{y}$ with $y_i = a < y_j, y_k \leq p$, $F_2(\vec{y}) = \med(y_j, y_k, p) = \max\{y_j, y_k\}$. We next show that this implies that for any instance $\vec{x}$ with $x_i = a < x_j, x_k \leq p$, $F_2(\vec{x}) = \max\{x_j, x_k\}$.

We fix an agent $i$ and a location $a \in \reals$, and let $\l_p(i, a) = p$. For sake of contradiction, let us assume that there is an instance $\vec{x}$, with $a= x_i < x_j < x_k \leq p$, such that $F_2(\vec{x}) \neq x_k$ (the case where $a < x_k < x_j \leq p$ is symmetric, while if $a < x_j = x_k \leq p$, then $F_2(\vec{x}) = x_k$, because $F$ has a bounded approximation ratio).
%
Therefore, $x_k$ does not belong to the image set $I_k(x_i, x_j)$, and there is a $x_k$-hole $(l, r)$ in $I_k(x_i, x_j)$.
%
%We note that $x_j \leq l$, since $x_j \in F(x_i, x_j, x_j)$, due to $F$'s bounded approximation ratio.
%
For an appropriately small $\eps \in (0, \min\{(r-l)/2, x_k-l\})$, we consider the instance $\vec{x}' = (\vec{x}_{-k}, l+\eps)$. Since $l+\eps$ is in the left half of the $x_k$-hole, $l \in F(\vec{x}')$.
%
Now, we consider the instance $\vec{x}'' = (\vec{x}_{-\{j,k\}}, l, l+\eps)$, and show that $F$ places its two facilities at $l$ and $l+\eps$. On the one hand, $l \in F(\vec{x}'')$, because $F$ is strategyproof. On the other hand, we can choose $\eps$ small enough that the instance $\vec{x}''$ is $(i|j,k)$-well-separated. Then, by Lemma~\ref{l:i-separated}, $x''_k \in F(\vec{x}'')$, because by the choice of $\eps$, $x''_j < x''_k < p$. However, this implies that $x_i$ is served by the facility at $l$, which contradicts $F$'s bounded approximation ratio.
\qed

%\subsection{The Proof of Lemma~\ref{l:approx}}
%\label{app:s:approx}


%\subsection{The Proof of Lemma~\ref{l:always-a}}
%\label{app:s:always-a}


\subsection{The Proof of Lemma~\ref{l:others-a}}
\label{app:s:others-a}

We only consider the case where $\l(i, a) = (j, a)$, and show that $\r(k, b) = (j, b)$, for the third agent $k$ and all locations $b$. The symmetric case follows from a symmetric argument.
%
Let $i$ be an agent and $a$ be a location such that $\l(i, a) = (j, a)$, for some agent $j$, and let $b$ be any location of the third agent $k$. Without loss of generality, we assume that $a < b$. Otherwise, we select a location $a'$ of $i$ with $a' < b$, and have that $\l(i, a') = (j, a')$, by Lemma~\ref{l:always-a}. To establish the lemma, we consider an instance $\vec{x}$ defined as $x_i = a$, $x_k = b$, and $x_j = a+\eps$, where $\eps > 0$ is chosen small enough that $\vec{x}$ is an $(i,j|k)$-well-separated instance. Since $x_j \geq \l_p(i, a)$, Lemma~\ref{l:non-separated} implies that $x_j \in F(\vec{x})$. Then, since $\vec{x}$ is an $(i,j|k)$-well-separated instance, by Proposition~\ref{prop:dict-location-a}, $\r(k, b) = (j, b)$. \qed


\subsection{The Proof of Lemma~\ref{l:only-dictator}}
\label{app:s:only-dictator}

We only show that for all locations $b$, $\l(j, b) =\,\uparrow$. The claim that $\r(j, b) =\,\downarrow$ follows from a symmetric argument.
%
In the following, we let $(i, a)$ be any agent-location pair with $\l_p(i, a) = (j, a)$, and let $k$ be the third agent. We observe that for all locations $a' \in \reals$, $\l(i, a') = (j, a')$, by Lemma~\ref{l:always-a}, and $\r(k, a') = (j, a')$, by Lemma~\ref{l:others-a}.
%
For sake of a contradiction, we assume that for some location $b \in \reals$, $\l_p(j, b) = b$. Therefore, there exists a (unique) preferred agent $\ell \in \{i, k\}$ such that $\l(j, b) = (\ell, b)$, and by Lemma~\ref{l:always-a}, for all locations $b' \in \reals$, $\l(j, b') = (\ell, b')$. Moreover, for all instances $\vec{x}$ with $x_j = b < \min\{ x_i, x_k \}$, Lemma~\ref{l:non-separated} implies that $x_\ell \in F(\vec{x})$. To reach a contradiction, we next show that $\l_\ell(j, b) \neq i$ and that $\l_\ell(j, b) \neq k$.

To this end, we first assume that $\l_\ell(j, b) = i$, and consider an instance $\vec{y}$ with $y_j = 0$, $y_k = 1$, and $y_i = \eps$, where $\eps > 0$ is chosen small enough that $\vec{y}$ is an $(j,i|k)$-well-separated instance.
%
Since $\l(j, 0) = (i, 0)$, since $j$ is the leftmost agent, and since $y_i > 0$, Lemma~\ref{l:non-separated} implies that $y_i \in F(\vec{x})$.
%
Moreover, since $\r(k, 1) = (j, 1)$, $k$ is the rightmost agent, and $y_j < 1$, the symmetric version of Lemma~\ref{l:non-separated} implies that $y_j \in F(\vec{x})$. Therefore, the agent $k$ is served by the facility at $y_i$, which contradicts $F$'s bounded approximation ratio, because the instance $\vec{y}$ is $(j,i|k)$-well-separated. %Consequently, $\l_\ell(j, b) \neq i$.

We have also to consider the case where $\l_\ell(j, b) = k$. In this case, we consider an instance $\vec{z}$ with $z_i = 0$, $z_j = 1$, and $z_k = 1+\eps$, where $\eps > 0$ is chosen small enough that $\vec{z}$ is an $(i|j,k)$-well-separated instance.
%
Since $\l(i, 0) = (j, 0)$, $i$ is the leftmost agent in $\vec{z}$, $z_j > 0$, and the instance $\vec{z}$ is $(i|j,k)$-well-separated, Lemma~\ref{l:i-separated} implies that $F_2(\vec{z}) = z_j$.
%
Therefore, $z_k \not\in F(\vec{z})$, and there is a $z_k$-hole $(l, r)$ in the imageset $I_k(z_i, z_j)$ with $l = 1$. We now consider the instance $\vec{z}' = (\vec{z}_{-\{i,k\}}, r, r-\delta)$, where $\delta > 0$ is chosen small enough that $r-\delta$ is in the right half of the hole $(l, r)$ and $\vec{z}'$ is an $(j|k,i)$-well-separated instance. We observe that $F(\vec{z}') = (r-\delta, r)$.
%
More specifically, $r = z'_i \in F(\vec{z}')$, due to $F$'s strategyproofness. Otherwise, the agent $i$ could switch to location $z_i$ and have $r \in F(\vec{z}'_{-i}, z_i)$, since $r$ is the closest point to $z'_k = r-\delta$ in the imageset $I_k(z_i, z_j)$.
%
Furthermore, since $\l(j, 1) = (k, 1)$, since $j$ is the leftmost agent in $\vec{z}'$, and since $z'_k > 1$, Lemma~\ref{l:non-separated} implies that $r-\delta = z'_k \in F(\vec{z}')$.
%
Therefore, the agent $j$ is served by the facility at $z'_k$, which contradicts $F$'s bounded approximation ratio, because the instance $\vec{z}'$ is $(j|k,i)$-well-separated. %Hence, $\l_\ell(j, b) \neq k$.
\qed


\subsection{The Rest of the Proof of Lemma~\ref{l:3agents}}
\label{app:s:3agents-lemma}

In Case II, where there is an agent-location pair $(i, a)$ with $\l_p(i, a) = a$, we have also to determine the facility allocation for instances $\vec{x}$ where $x_k < x_i$. To this end, we first show that either $\l(k, b) = (j, b)$ or $\l_p(k, b) =\,\uparrow$, for all locations $b$ (i.e., we exclude the possibility that for some location $b$, $\l(k, b) = (i, b)$).

To reach a contradiction, let us assume that for some location $b$, $\l(k, b) = (i, b)$. Let $\vec{y}$ be any $(k,i|j)$-well-separated instance with $y_k = b$. Since $\l(k, b) = (i, b)$, since $k$ is the leftmost agent in $\vec{y}$, and since $y_i > b$, Lemma~\ref{l:non-separated} implies that $y_i \in F(\vec{y})$.
%
Moreover, since $\r(j, y_j) =\,\downarrow$, and since $j$ is the rightmost and $y_k$ is the leftmost agent in $\vec{y}$, the symmetric version of Lemma~\ref{l:non-separated-inside} implies that $y_k \in F(\vec{y})$. Therefore, the agent $j$ is served by the facility at $y_i$, which contradicts $F$'s bounded approximation ratio, because $\vec{y}$ is an $(k,i|j)$-well-separated instance.

To conclude the proof, we distinguish between the case where there is a location $b$ such that $\l(k, b) = (j, b)$, and the case where for all locations $b$, $\l_p(k, b) =\,\uparrow$.
%
We recall that $\l_p(j, b) =\,\uparrow$ and $\r_p(j, b) =\,\downarrow$, for all locations $b$, by Lemma~\ref{l:only-dictator}, because $\l(i, a) = (j, a)$.

If there is a location $b$ such that $\l(k, b) = (j, b)$, then for all locations $b' \in \reals$, $\l(k, b') = (j, b')$, by Lemma~\ref{l:always-a}, and $\r(i, b') = (j, b')$, by Lemma~\ref{l:others-a}. Therefore, for all instances $\vec{x}$ with $x_k < x_i$, $x_j \in F(\vec{x})$. More specifically, if $x_k < x_j$, this follows from Lemma~\ref{l:non-separated}, while if $x_j < x_i$, this follows from the symmetric version of Lemma~\ref{l:non-separated}. Then, % as before,
we use Lemma~\ref{l:non-separated-inside}, and obtain the conclusion of the lemma for all instances $\vec{x}$ with $x_k < x_i$\,:

\begin{itemize}
\item For all instances $\vec{x}$ with $x_k < x_j < x_i$, $x_j \in F(\vec{x})$.

\item For all instances $\vec{x}$ with $x_j < x_k < x_i$, $F_1(\vec{x}) = x_j$ and $F_2(\vec{x}) = x_i$, by Lemma~\ref{l:non-separated-inside}, because $\l_p(j, x_j) =\,\uparrow$. Therefore, $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$.

\item For all instances $\vec{x}$ with $x_k < x_i < x_j$, $F_2(\vec{x}) = x_j$ and $F_1(\vec{x}) = x_k$, by the symmetric version of Lemma~\ref{l:non-separated-inside}, because $\r_p(j, x_j) =\,\downarrow$. Therefore, $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$.
\end{itemize}


Otherwise, for all locations $b$, $\l_p(k, b) =\,\uparrow$. We observe that for all locations $b$, $\r_p(i, b) =\,\downarrow$. Otherwise, there would exist a location $b'$ with $\r_p(i, b') = b'$, by Lemma~\ref{l:i-cases}, and thus $\l_p(k, b') = b'$, by Lemma~\ref{l:others-a}, a contradiction.
%
As before, we now use Lemma~\ref{l:non-separated-inside}, and obtain the conclusion of the lemma for all instances $\vec{x}$ with $x_k < x_i$. More specifically, since $x_k < x_i$, the leftmost agent of $\vec{x}$ is either $k$ or $j$. If the leftmost agent is $k$ (resp. $j$), $F_2(\vec{x}) = \max\vec{x}$, by Lemma~\ref{l:non-separated-inside}, because $\l_p(k, x_k) =\,\uparrow$ (resp. $\l_p(j, x_j) =\,\uparrow$).
%
Similarly, the rightmost agent of $\vec{x}$ is either $j$ or $i$. If the rightmost agent is $j$ (resp. $i$), $F_1(\vec{x}) = \min\vec{x}$, by the symmetric version of Lemma~\ref{l:non-separated-inside}, because $\r_p(j, x_j) =\,\downarrow$ (resp.
$\r_p(i, x_i) =\,\downarrow$).
%
%Again, we use Lemma~\ref{l:non-separated-inside}, and obtain the conclusion of the lemma for all instances $\vec{x}$ with $x_k < x_i$\,:
%
%\begin{itemize}
%\item For all instances $\vec{x}$ with $x_j < x_k < x_i$, $F_1(\vec{x}) = x_j$, by the symmetric version of Lemma~\ref{l:non-separated-inside}, because $\r_p(i, x_i) =\,\downarrow$, and $F_2(\vec{x}) = x_i$, by Lemma~\ref{l:non-separated-inside}, because $\l_p(j, x_j) =\,\uparrow$.
%
%\item For all instances $\vec{x}$ with $x_k < x_j < x_i$, $F_1(\vec{x}) = x_k$, by the symmetric version of Lemma~\ref{l:non-separated-inside}, because $\r_p(i, x_i) =\,\downarrow$, and $F_2(\vec{x}) = x_i$, by Lemma~\ref{l:non-separated-inside}, because $\l_p(k, x_k) =\,\uparrow$.
%
%\item For all instances $\vec{x}$ with $x_k < x_i < x_j$, $F_1(\vec{x}) = x_k$, by the symmetric version of Lemma~\ref{l:non-separated-inside}, because $\r_p(j, x_j) =\,\downarrow$, and $F_2(\vec{x}) = x_j$, by Lemma~\ref{l:non-separated-inside}, because $\l_p(k, x_k) =\,\uparrow$.
%\end{itemize}
%
Thus, if $\l_p(k, b) =\,\uparrow$, for all instances $\vec{x}$ with $x_k < x_i$, $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$.
 \qed





